\documentclass[xcolor=pdflatex,dvipsnames,table]{beamer}
\usepackage{epsfig,graphicx}
\usepackage{palatino}
\usepackage{fancybox}
\usepackage{relsize}
\usepackage[procnames]{listings}

\input{../style/scala.tex}
\input{../style/stanza.tex}
\input{../style/talk.tex}

\title{Chipper Bootcamp}
\author{Jonathan Bachrach}
\date{\today}
\institute[UC Berkeley]{EECS UC Berkeley}

\begin{document}

\begin{frame}
\titlepage
\end{frame}
\addtocounter{framenumber}{-1}

\begin{frame}[fragile]{Goals for Bootcamp}

\begin{itemize}
\item introduction to reconfigurable computing
\item introduction to hardware design
\item introduce you to stanza
\item get you started with Chipper
\item get a basic working knowledge of Chipper
\item learn how to think in Chipper
\item how to write an accelerator
\item know where to get more information
\end{itemize}

\end{frame}

\begin{frame}[fragile]{What is Digital Hardware Design?}

{\bf Register Transfer Level = RTL}
\begin{columns}
\column{0.45\textwidth}
\begin{itemize}
\item logic and state 
\item state machines
\end{itemize}
\column{0.45\textwidth}
\begin{itemize}
\item e.g., adders and registers
\item e.g., counter example:
\end{itemize}
\end{columns}
\begin{columns}
\column{0.45\textwidth}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/rtl.pdf} \\
\end{center}
\column{0.45\textwidth}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/simple-counter.pdf} \\[0.5cm]
\end{center}
\end{columns}

\begin{center}
\includegraphics[height=0.2\textheight]{figs/rtl-timing.pdf} \\
synchronous clock
\end{center}
\note{because this is a PL seminar will start with simple view of design \\[0.125cm]
designs can be roughly split into logic and state forming state machines \\[0.125cm]
where logic gives next state values \\[0.125cm]
there is a synchronous clock and \\[0.125cm]
next state is committed on rising edge \\[0.125cm]
this modeling of digital design is called RTL \\[0.125cm]
example is counter state where logic increments counter \\[0.125cm]
complexity comes from two sources \\[0.125cm]
one: want to run fast and compute has to complete in one period \\[0.125cm]
compute has to be broken up into chunks of work \\[0.125cm]
two: need to coordinate updates on state from parallel mutators \\[0.125cm]
writing hardware is not for faint of heart}
\end{frame}

\begin{frame}[fragile]{HW Design Context}
\begin{center}
\includegraphics[height=0.7\textheight]{figs/apps-machines-realizations.pdf}
\end{center}
\begin{itemize}
\item what's best machine?
\item how to most efficiently implement machine? 
% \item just take compute graph and unroll all loops
% \item map all compute to logic and memory to state
\end{itemize}
% {\footnotesize * consider machine fast application specific interpreter}
\note{what we really want is to make apps go faster \\[0.5cm]
split problem into mapping app machine and machine to gates \\[0.5cm]
hardware design is focussed on creating and implementing machines that \\[0.5cm]
could be thought of as fast app accelerators 
}
\end{frame}

\begin{frame}[fragile]{Three Hard HLS* Tasks}
\begin{center}
\includegraphics[height=0.7\textheight]{figs/apps-realizations.pdf} \\[0.5cm]
\end{center}
would love to go app -> gates but ... it's really hard \\[0.5cm]
* HLS = High Level Synthesis

% \begin{itemize}
% \item deciding which compute resources should be allocated
% \item split it into small enough chunks to have fast enough clock
% \item scheduling compute onto them at clock level
% \end{itemize}
\note{would love to have a sufficiently smart compiler but \\[0.5cm]
involves a couple intractable problems
}
\end{frame}

\begin{frame}[fragile]{Opportunity Is Huge}
\begin{columns}
\column{0.45\textwidth}
\begin{center}
\includegraphics[height=0.3\textheight]{figs/smart-phone.jpeg} 
\includegraphics[height=0.3\textheight]{figs/red-refrigerator-big-chill.jpg} \\
\end{center}
\column{0.45\textwidth}
\begin{center}
\includegraphics[height=0.3\textheight]{figs/globe.jpg} 
\end{center}
\end{columns}
\vspace{0.5cm}
\begin{itemize}
\item use 10\% of energy
\item yearly power use of phone == refridgerator
\item cost of computing infrastructure is often < yearly energy bill
\item only starting to bring world online \\[0.5cm]
\item \color{red}{energy is starting to dominate everything!!!} \\[0.25cm]
\item \color{red}{digital designs yield 100-1000x win in efficiency} \\[0.5cm]
\end{itemize}
\note{based on time magazine article \\[0.5cm]
*** your mileage might vary but ... still}
\end{frame}

\begin{frame}[fragile]{Hardware Designers}
\begin{center}
\includegraphics[height=0.6\textheight]{figs/i286-team.png}
\end{center}
\begin{itemize}
\item mostly EE backgrounds
\item very little PL experience
\item efficiency is everything!
\end{itemize}
\note{challenge of doing an HDL}
\end{frame}

\begin{frame}[fragile]{Dire Hardware Design Situation}
\begin{itemize}
\item slow hardware design
\begin{itemize}
\item 1980's style languages and baroque tool chains with ad hoc scripts
\item manual optimization obscuring designs
\item minimal compile-time and run-time errors
\item army of people in both CAD tools and design -- costs \$10Ms
\end{itemize}
\item slow and expensive to synthesize
\begin{itemize}
\item takes order days
\item not robust and so largely manual process
\item proprietary tools -- cost > \$1M / year / seat
\end{itemize}
\item slow testing and evaluation
\begin{itemize}
\item runs 200M x slower than code runs in production
\item army of verification people -- costs \$10Ms
\end{itemize}
\item slow and expensive fabrication
\begin{itemize}
\item very labor intensive -- costs \$1Ms \\[0.5cm]
\end{itemize}
\item {\color{red}design costs dominate}
\item {\color{red}very few ASIC designs and chip startups}
% \item but ...
% \begin{itemize}
% \item can use higher level tools but hard to know performance
% \item can run untranslated code 2M x slower
% \item can fab to FPGA through worse tools
% \end{itemize}
\end{itemize}
\note{extremely painful state of affairs}
\end{frame}

\begin{frame}[fragile]{Imagine If In Software Design}
\begin{itemize}
\item had to program in assembly language (or fortran)
\item compilation took hours or days
\item got minimal compile or run time warnings or errors
\item finding bugs took hours or weeks
\item burning ``CD''s cost \$1Ms 
\end{itemize}
\begin{columns}
\column{0.55\textwidth}
\begin{itemize}
\item {\color{red}Software startups would be rare}
\item {\color{red}CS enrollment would go way down!}
\end{itemize}
\column{0.35\textwidth}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/punch-cards.jpg}
\end{center}
\end{columns}
\note{to put it in perspective ...}
\end{frame}

\begin{frame}[fragile]{Imagine If In Hardware Design}
\begin{itemize}
\item could build a ``chip'' in an hour (or a day) *
\item build and fab tools were low cost (or free) *
\item could create reusable and abstract modules
\item had large library of standard components to choose from
\item could create chips with small teams
\end{itemize}
\begin{columns}
\column{0.6\textwidth}
\begin{itemize}
\item {\color{red}Hardware startups would be common}
\item {\color{red}EE enrollment might go way up!}
\end{itemize}
\column{0.3\textwidth}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/clay-power.jpg}
\end{center}
\end{columns}
\vspace{1cm}
{\it\small * FPGAs almost fit the bill but tools are painful to use and painfully slow}
\note{wouldn't it be great if ...}
\end{frame}

\input{reconfigurable.tex}

\begin{frame}[fragile]
\frametitle{Status Quo Generators}
\begin{enumerate}
\item write verilog design structurally -- literal
\item verilog generate command -- limited
\item write perl script that writes verilog -- awkward
\end{enumerate}
\begin{columns}
\column{0.45\textwidth}
\begin{scala}
module counter (clk, reset);
  input clk;
  input reset;
  parameter W = 8;
  reg [W-1:0] cnt;
  always @ (posedge clk)
  begin
    if (reset)
      cnt = 0
    else
      cnt = cnt + 1
  end
endmodule
\end{scala}
% \begin{scala}
% module counter (clk, reset);
%   input clk;
%   input reset;
%   parameter W   = 8;
%   parameter LIM = (1<<W)-1;
%   reg   [W-1:0] cnt;
%   always @ (posedge clk)
%   begin
%     if (reset || cnt == LIM)
%       cnt = 0
%     else
%       cnt = cnt + 1
%   end
% endmodule
% \end{scala}
\column{0.45\textwidth}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/counter-width.pdf}
\end{center}
\end{columns}
\note{designers want to parameterize their designs \\[0.5cm]
allow structural design parameters \\[0.5cm]
ad hoc parameterized generation of circuits \\[0.5cm]
when need more powerful construction people write perl scripts to write verilog}
\end{frame}

\input{chisel-overview.tex}

\begin{frame}[fragile]
\frametitle{Chipper}

\begin{columns}[c]

\column{0.55\textwidth}

\begin{itemize}
\item A hardware construction language 
\begin{itemize}
\item ``synthesizable by construction''
\item creates graph representing hardware
\end{itemize}
\item Embedded within Stanza language to leverage mindshare and language design
\item Best of hardware and software design ideas
\item Multiple targets
\begin{itemize}
\item Simulation and synthesis
\item Memory IP is target-specific \\[0.5cm]
\end{itemize}
\item {\color{red}{\bf Not} Stanza app -> Verilog arch}
\end{itemize}

\column{0.40\textwidth}

\begin{center}
single source \\
\includegraphics[width=0.99\textwidth]{figs/graph-and-targets.pdf} \\
multiple targets \\
\end{center}

\end{columns}
\note{creates a graph if successfully created will correctly synthesize \\[1cm]
single source generates two different verilog outputs, one for fpga and one for asic. \\[1cm]
surprisingly difficult to generate each.  for example, chipper has abstraction for memories.}
\end{frame}

\include{stanza-pitch}
\include{stanza-intro}

\begin{frame}[fragile]
\frametitle{Algebraic Graph Construction}

\begin{columns}
\column{0.35\textwidth}
{\lstset{basicstyle={\Large\ttfamily}}
\begin{stanza}
mux(x > y, x, y)
\end{stanza}
}

\column{0.6\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/max2.pdf} 
\end{center}
\end{columns}
\end{frame}

\begin{frame}[fragile]
\frametitle{Creating Module}

\begin{columns}
\column{0.45\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule Max2 :
  input x : UInt<8>
  input y : UInt<8>
  output z : UInt<8>
  io.z := mux(io.x > io.y, io.x, io.y)
\end{stanza}
}

\column{0.45\textwidth}
\begin{center}
\includegraphics[width=0.95\textwidth]{figs/Max2c.pdf} \\
\end{center}
\end{columns}

\end{frame}

\begin{frame}[fragile]
\frametitle{Connecting Modules}

\begin{columns}
\column{0.3\textwidth}
\begin{stanza}
inst m1 : Max2()
m1.x := a
m1.y := b
inst m2 : Max2()
m2.x := c
m2.y := d
inst m3 : Max2()
m3.x := m1.z
m3.y := m2.z
\end{stanza}

\column{0.6\textwidth}

\begin{center}
\includegraphics[width=0.99\textwidth]{figs/Max4.pdf} \\
\end{center}
\end{columns}

\end{frame}


\begin{frame}[fragile]
\frametitle{Defining Construction Functions}

\begin{columns}

\column{0.45\textwidth}

\begin{stanza}
defn max2 (x, y): mux(x > y, x, y)
\end{stanza}
\begin{stanza}
max2(x, y)
\end{stanza}

\column{0.5\textwidth}

\begin{center}
\includegraphics[width=0.95\textwidth]{figs/Max2.pdf} \\[1cm]
\end{center}

\end{columns}

\end{frame}

\begin{frame}[fragile]
\frametitle{Functional Construction}

\begin{columns}

\column{0.5\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule MaxN (n:Int, w:Int) :
  input in : UInt<w>[n]
  output out : UInt<w>
  out := reduce(max2, in)

...

inst mx4 : Max4(4, w)
mx4.in[0] := a
mx4.in[1] := b
mx4.in[2] := b
mx4.in[3] := c
\end{stanza}
}

\column{0.4\textwidth}

\begin{center}
\includegraphics[width=0.99\textwidth]{figs/reduceMax.pdf} \\
\end{center}

\end{columns}

\end{frame}

% \input{lib-to-langs-guts-in-stanza.tex}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Bootcamp Chipper Installation}
\begin{stanza}
-Install VirtualBox
-File->Import appliance, chipper-vm.ova
-Start
-Login (username: chipper-bootcamp, password: chipper)
-GTKWave, Emacs, etc. all installed
\end{stanza}
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Updating the Chipper Tutorial}

\begin{stanza}
cd ucb-bar/chipper-tutorial
git pull
cd ../chipper
git pull
\end{stanza}
% bin/install.sh
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Chipper Tutorial Contents}
{\lstset{basicstyle={\small\ttfamily}}
\begin{FramedSemiVerb}
chipper-tutorial/  
  Makefile
  generated/
    examples/
    problems/
    solutions/
  src/        \comment{\# Contains shared code}
    use-chipper.stanza ...
  examples/   \comment{\# Contains chipper examples}
    Makefile  
    FullAdder.stanza ...
  problems/   \comment{\# Contains skeletal files for tutorial problems}
    Makefile
    Accumulator.stanza ...
  solutions/  \comment{\# Contains solutions to problems}
    Makefile
    Counter.stanza ...
\end{FramedSemiVerb}
}
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Test It}

\begin{bash}
cd $TUT_DIR/examples
make ByteSelector.out
\end{bash}

% \begin{bash}
% cd $TUT_DIR/examples
% make check Parity.out
% \end{bash}

\vspace{1cm}
\noindent
If your system is set up correctly, you should see a messsage \verb+SUCCESS+
% followed by the total time of the run, and date and time of completion. 

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}


\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Get This}

\begin{bash}
open chipper-tutorial/chipper/doc/bootcamp/bootcamp.pdf
\end{bash}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]
\frametitle{Example}
\begin{columns}

\column{0.45\textwidth}

\begin{footnotesize}
\begin{stanza}
defmodule GCD :
  input a      : UInt<16>
  input b      : UInt<16>
  output z     : UInt<16>
  output valid : UInt<1>
  reg x = a
  reg y = b
  when x > y :
    x := x - y
  else :
    y := y - x
  z     := x
  valid := y === UInt(0)
\end{stanza}
\end{footnotesize}

\column{0.45\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/gcd.pdf} 
\end{center}

\end{columns}
\end{frame}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Running the Chipper Simulation}

\begin{bash}
cd ~/chipper-tutorial/examples
make GCD.out
\end{bash}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{bash}
...
SUCCESS
\end{bash}
% [success] Total time: 2 s, completed Feb 28, 2013 8:14:37 PM
}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Generating Verilog}

\begin{bash}
cd ~/chipper-tutorial/examples
make GCD.v
\end{bash}

The Verilog source is roughly divided into three parts:

\begin{enumerate}
\item Module declaration with input and outputs
\item Temporary wire and register declaration used for holding intermediate values
\item Register assignments in \verb+always @ (posedge clk)+
\end{enumerate}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{FullAdder -- Type Inference}

\begin{columns}
\column{0.4\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule FullAdder :
  input a: UInt<1>
  input b: UInt<1>
  input cin: UInt<1>
  output sum: UInt<1>
  output cout: UInt<1>
  ;; Generate the sum
  wire a_xor_b = a ^ b
  sum := a_xor_b ^ io.cin
  ;; Generate the carry
  wire a_and_b   = a & b
  wire b_and_cin = b & cin
  wire a_and_cin = a & cin
  cout := a_and_b |
    b_and_cin | a_and_cin
\end{stanza}
}

\column{0.55\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{../getting-started/figs/Full_Adder.jpg}
\end{center}

\end{columns}

\end{frame}

\begin{frame}[fragile]{FullAdder Verilog -- Width Inference 1}

\begin{columns}
\column{0.45\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule FullAdder :
  input a: UInt<1>
  input b: UInt<1>
  input cin: UInt<1>
  output sum: UInt<1>
  output cout: UInt<1>
  ;; Generate the sum
  wire a_xor_b = a ^ b
  sum := a_xor_b ^ io.cin
  ;; Generate the carry
  wire a_and_b   = a & b
  wire b_and_cin = b & cin
  wire a_and_cin = a & cin
  cout := a_and_b |
    b_and_cin | a_and_cin
\end{stanza}
}

\column{0.45\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
module FullAdder(
    input  io_a,
    input  io_b,
    input  io_cin,
    output io_sum,
    output io_cout);
  wire T0;
  wire a_and_cin;
  wire T1;
  wire b_and_cin;
  wire a_and_b;
  wire T2;
  wire a_xor_b;

  assign io_cout = T0;
  assign T0 = T1 | a_and_cin;
  assign a_and_cin = io_a & io_cin;
  assign T1 = a_and_b | b_and_cin;
  assign b_and_cin = io_b & io_cin;
  assign a_and_b = io_a & io_b;
  assign io_sum = T2;
  assign T2 = a_xor_b ^ io_cin;
  assign a_xor_b = io_a ^ io_b;
endmodule
\end{stanza}
}

\end{columns}

\end{frame}

\begin{frame}[fragile]{FullAdder2 Verilog -- Width Inference 2}

\begin{columns}
\column{0.45\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule FullAdder :
  input a: UInt<2>
  input b: UInt<2>
  input cin: UInt<2>
  output sum: UInt<2>
  output cout: UInt<1>
  ;; Generate the sum
  wire a_xor_b = a ^ b
  sum := a_xor_b ^ io.cin
  ;; Generate the carry
  wire a_and_b   = a & b
  wire b_and_cin = b & cin
  wire a_and_cin = a & cin
  cout := a_and_b | b_and_cin | a_and_cin
\end{stanza}
}

\column{0.45\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
module FullAdder(
    input [1:0] io_a,
    input [1:0] io_b,
    input [1:0] io_cin,
    output[1:0] io_sum,
    output[1:0] io_cout);
  wire[1:0] T0;
  wire[1:0] a_and_cin;
  wire[1:0] T1;
  wire[1:0] b_and_cin;
  wire[1:0] a_and_b;
  wire[1:0] T2;
  wire[1:0] a_xor_b;

  assign io_cout = T0;
  assign T0 = T1 | a_and_cin;
  assign a_and_cin = io_a & io_cin;
  assign T1 = a_and_b | b_and_cin;
  assign b_and_cin = io_b & io_cin;
  assign a_and_b = io_a & io_b;
  assign io_sum = T2;
  assign T2 = a_xor_b ^ io_cin;
  assign a_xor_b = io_a ^ io_b;
endmodule
\end{stanza}
}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Using Registers}
\begin{stanza}
// clock the new reg value on every cycle
wire y = x
reg z := y
\end{stanza}

\begin{stanza}
// clock the new reg value when the condition a > b
reg x : UInt
when a > b :
  x := y 
else when b > a :
  x := z
else :
  x := w
\end{stanza}
\end{frame}

\begin{frame}[fragile]{Unconditional Register Update}

\begin{columns}

\column{0.42\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule ShiftRegister :
  input in : UInt<1>
  output out : UInt<1>
  reg r0 := in
  reg r1 := r0
  reg r2 := r1
  reg r3 := r2
  out := r3
\end{stanza}
}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/shift-register.pdf}
\end{center}

\column{0.5\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
module ShiftRegister(input clk, input reset,
    input  io_in,
    output io_out);

  reg[0:0] r3;
  reg[0:0] r2;
  reg[0:0] r1;
  reg[0:0] r0;

  assign io_out = r3;
  always @(posedge clk) begin
    r3 <= r2;
    r2 <= r1;
    r1 <= r0;
    r0 <= io_in;
  end
endmodule
\end{stanza}
}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Conditional Register Update}

\begin{columns}

\column{0.47\textwidth}

\begin{stanza}
defmodule ShiftRegisterCond :
  input in : UInt<1>
  input shift : UInt<1>
  output out : UInt<1>

  reg r0 : UInt<1>
  reg r1 : UInt<1>
  reg r2 : UInt<1>
  reg r3 : UInt<1>

  when shift :
    r0 := in
    r1 := r0
    r2 := r1
    r3 := r2
  out := r3
\end{stanza}

\column{0.45\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/enable-shift-register.pdf}
\end{center}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Conditional Register Update with Reset}

\begin{stanza}
defmodule ShiftRegisterCondInit :
  input in : UInt<1>
  input shift : UInt<1>
  output out : UInt<1>

  ;; Register reset to zero
  reg r0 = UInt<1>(0)
  reg r1 = UInt<1>(0)
  reg r2 = UInt<1>(0)
  reg r3 = UInt<1>(0)

  when shift :
    r0 := in
    r1 := r0
    r2 := r1
    r3 := r2
  out := r3
\end{stanza}

\end{frame}

\begin{frame}[fragile]{UInt Literals}
inferred width
\begin{stanza}
UInt(1)       ;; decimal 1-bit literal from Stanza Int. 
UInt("ha")    ;; hexadecimal 4-bit literal from string.
UInt("o12")   ;; octal 4-bit literal from string. 
UInt("b1010") ;; binary 4-bit literal from string.
\end{stanza}
specified widths
\begin{stanza}
UInt("h_dead_beef") ;; 32-bit literal of type UInt.
UInt(1)             ;; decimal 1-bit literal from Stanza Int.
UInt<8>("ha")       ;; hexadecimal 8-bit literal of type UInt.
UInt<6>("o12")      ;; octal 6-bit literal of type UInt.
UInt<12>("b1010")   ;; binary 12-bit literal of type UInt.
UInt<8>(5)          ;; unsigned decimal 8-bit literal of type UInt.
\end{stanza}
\end{frame}


\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Sequential Circuit Problem -- \tt Accumulator.stanza}
\begin{itemize}
\item write sequential circuit that sums \code{in} values
\item in {\tt chipper-tutorial/problems/Accumulator.stanza}
\item run {\tt make Accumulator.out} until passing
\end{itemize}
\begin{stanza}
defmodule Accumulator :
  input in : UInt<1>
  output out : UInt<8>

  ;; flush this out ...

  out := UInt(0)
\end{stanza}
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{UInt Operations and Conditional Assignment}

\begin{columns}
\column{0.5\textwidth}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defmodule BasicALU :
  input a      : UInt<4>
  input b      : UInt<4>
  input opcode : UInt<4>
  output out = UInt<4>
  out := UInt(0) 
  when opcode === UInt(0) :
    out := a                   ;; pass A
  else when opcode === UInt(1) :
    out := b                   ;; pass B
  else when: opcode === UInt(2) :
    out := a + UInt(1)         ;; inc A by 1
  else when: opcode === UInt(3) :
    out := a - UInt(1)         ;; dec B by 1
  else when: opcode === UInt(4) :
    out := a + UInt(4)         ;; inc A by 4
  else when: opcode === UInt(5) :
    out := a - UInt(4)         ;; dec A by 4
  else when: opcode === UInt(6) :
    out := a + b               ;; add A and B
  else when: opcode === UInt(7) :
    out := a - b               ;; sub B from A
  else when: opcode === UInt(8) :
    out := (a < b)             ;; set on A < B
  else :
    out := (a === b)           ;; set on A == B
\end{stanza}
}

\column{0.4\textwidth}
\begin{itemize}
\item wire \code{io.output} defaulted to 0 and then
\item conditionally reassigned to based on opcode
\item unlike registers, wires are required to be defaulted
\item wires also allow forward declarations
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}[fragile]{UInt Operations}

\begin{center}
\begin{tabular}{| c | c | }
\hline
Symbol & Operation \\ \hline
\verb!+! & Add \\ \hline
\verb+-+ & Subtract \\ \hline
\verb+*+ & Multiply \\ \hline
\verb+/+ & UInt Divide \\ \hline
\verb+%+ & Modulo \\ \hline
\verb+!+ & Bitwise Negation \\ \hline
\verb+^+ & Bitwise XOR \\ \hline
\verb+&+ & Bitwise AND \\ \hline
\verb+|+ & Bitwise OR \\ \hline
{\color{red}\verb+===+} & Equal \\ \hline
\verb+!==+ & Not Equal \\ \hline
\verb+>+ & Greater \\ \hline
\verb+<+ & Less \\ \hline
\verb+>=+ & Greater or Equal \\ \hline
\verb+<=+ & Less or Equal \\ \hline
\end{tabular}
\end{center}

\end{frame}

\begin{frame}[fragile]{Bit Extraction}
\begin{stanza}
;; extracts the lo through hi bits of value
wire x_to_y = value[hi, lo]
\end{stanza}

\begin{stanza}
;; extract the x-th bit from value
wire x_of_value = value[x]
\end{stanza}
\end{frame}

\begin{frame}[fragile]{ByteSelector}

\begin{stanza}
defmodule ByteSelector :
  input in: UInt<32>
  input off: UInt<2>
  output out: UInt<8>

  when off === UInt(0) :
    out := in[7,0]
  else when off === UInt(1) :
    out := in[15, 8]
  else when off === UInt(2) :
    out := in[23,16]
  else :
    out := in[31,24]
\end{stanza}

\end{frame}

% \setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
% \begin{frame}[fragile]{Instruction Decoder}
% 
% {\lstset{basicstyle={\scriptsize\ttfamily}}
% \begin{stanza}
% class LoadShiftRegister extends Module {
%   val io = new Bundle {
%     val inst  = UInt(INPUT, 32)
%     val rs0   = UInt(OUTPUT, 8)
%     val rs1   = UInt(OUTPUT, 8)
%     val rs2   = UInt(OUTPUT, 8)
%     val isAdd = Bool(OUTPUT)
%     val isSub = Bool(OUTPUT)
%     val isMul = Bool(OUTPUT)
%     val isDiv = Bool(OUTPUT)
%   }
%   io.isAdd := ...
%   io.isSub := ...
%   io.isMul := ...
%   io.isDiv := ...
%   io.rs0   := ...
%   io.rs1   := ...
%   io.rs2   := ...
% }
% \end{stanza}
% }
% 
% \end{frame}
% \setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{Bit Concatenation and Filling}
You concatenating bits using \verb+Cat+:
\begin{stanza}
wire A   : UInt<32>
wire B   : UInt<32>
wire bus = cat(A, B) ;; concatenate A and B
\end{stanza}

and replicate bits using \verb+Fill+:
\begin{stanza}
// Replicate a bit string multiple times.
val usDebt = Fill(3, UInt("hA")) 
\end{stanza}

\end{frame}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{LFSR16 -- \tt problems/lfsr16.stanza}

\begin{stanza}
defmodule LFSR16 :
  input inc : UInt<1>
  output out : UInt<16>
  ;; ...
  out := UInt(0)
\end{stanza}
\begin{itemize}
\item \verb+reg+, \verb+cat+, \verb+[]+, \verb+^+
\item init reg to 1
\item updates when \verb+inc+ asserted
\end{itemize}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/LFSR16.pdf}
\end{center}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{UInt Bit Inference}
\begin{columns}
\column{0.4\textwidth}
\begin{stanza}
defmodule HiLoMultiplier :
  input A  : UInt<16>
  input B  : UInt<16>
  output Hi : UInt<16>
  output Lo : UInt<16>
  wire mult = A * B
  Lo := mult[15, 0]
  Hi := mult[31, 16]
\end{stanza}

\column{0.5\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
module HiLoMultiplier(
    input [15:0] io_A,
    input [15:0] io_B,
    output[15:0] io_Hi,
    output[15:0] io_Lo);

  wire[15:0] T0;
  wire[31:0] mult; // inferred as 32 bits
  wire[15:0] T1;

  assign io_Lo = T0;
  assign T0 = mult[4'hf:1'h0];
  assign mult = io_A * io_B;
  assign io_Hi = T1;
  assign T1 = mult[5'h1f:5'h10];
endmodule
\end{stanza}
}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Bit Inference Rules}

\begin{center}
\begin{tabular}{| l | l | l | }
\hline
Operation & Result Bit Width \\ \hline
\verb!Z = X + Y! & \verb!max(width(X), width(Y))!  \\ \hline
\verb+Z = X - Y+ & \verb!max(width(X), width(Y))! \\ \hline
\verb+Z = X & Y+ & \verb!min(width(X), width(Y))! \\ \hline
\verb+Z = X | Y+ & \verb!max(width(X), width(Y))! \\ \hline
\verb+Z = X ^ Y+ & \verb!max(width(X), width(Y))! \\ \hline
\verb+Z = !(X)+ & \verb!width(X)! \\ \hline
\verb+Z = mux(C, X, Y)+ & \verb!max(width(X), width (Y))! \\ \hline
\verb+Z = X * Y+ & \verb!width(X)! + width(Y) \\ \hline
\verb+Z = X << n+ & \verb!width(X)! + n \\ \hline
\verb+Z = X >> n+ & \verb!width(X)! - n \\ \hline
\verb+Z = cat(X, Y)+ & \verb!width(X)! + width(Y) \\ \hline
\verb+Z = fill(n, x)+ & \verb!width(X)! + n \\ \hline
\end{tabular}
\end{center}

\end{frame}

\begin{frame}[fragile]{Bool Type}
The Chipper Bool is used to represent the result of logical expressions:
\begin{stanza}
wire change = io.a === io.b ;; change gets Bool type
when change : ;; execute if change is true
 ...
\end{stanza}

You can instantiate a Bool value like this:
\begin{stanza}
wire true_value  = UInt(true)
wire false_value = UInt(false)
\end{stanza}

\end{frame}

\begin{frame}[fragile]{Bits Subtype Hierarchy}
\begin{itemize}
\item \verb+SInt+ is a signed integer type
\end{itemize}
\begin{center}
\includegraphics[height=0.7\textheight]{figs/bits-hierarchy.pdf}
\end{center}
\end{frame}

\begin{frame}[fragile]{Bundles}

\begin{columns}
\column{0.55\textwidth}
\begin{stanza}
defbundle MyFloat :
  sign : UInt<1>
  exponent : UInt<8>
  significand : UInt<23>

wire x  : MyFloat
wire xs = x.sign
\end{stanza}

\column{0.35\textwidth}

\begin{center}
\includegraphics[height=0.9\textheight]{figs/myfloat.pdf} 
\end{center}

\end{columns}
\end{frame}

\begin{frame}[fragile]{Ports}

\begin{columns}
\column{0.55\textwidth}

\textbf{Data object with directions assigned to its members}

\begin{stanza}
defbundle Decoupled :
  data : UInt<32>
  valid : UInt<1>
  flip ready : UInt<1>
\end{stanza}

\textbf{Direction assigned at instantiation time}

\begin{stanza}
defbundle ScaleIO :
  flip in : MyFloat
  flip scale : MyFloat
  out : MyFloat
\end{stanza}

\column{0.35\textwidth}

\begin{center}
\includegraphics[height=0.9\textheight]{figs/FIFOIO.pdf} 
\end{center}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Instantiating Modules}

\begin{columns}

\column{0.4\textwidth}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
;; A 4-bit adder with carry in and carry out
defmodule Adder4:
  input A : UInt<4>
  input B : UInt<4>
  input Cin : UInt<1>
  output Sum : UInt<4>
  output Cout : UInt<1>
  ;; Adder for bit 0
  inst Adder0 : FullAdder
  Adder0.a   := A[0]
  Adder0.b   := B[0]
  Adder0.cin := Cin
  wire s0 = Adder0.sum
  ;; Adder for bit 1
  inst Adder1 = FullAdder
  Adder1.a   := A[1]
  Adder1.b   := B[1]
  Adder1.cin := Adder0.cout
  wire s1 = Cat(Adder1.sum, s0)
  ...
  ;; Adder for bit 3
  inst Adder3 : FullAdder
  Adder3.a   := A[3]
  Adder3.b   := B[3]
  Adder3.cin := Adder2.cout
  Sum  := Cat(Adder3.sum, s2)
  Cout := Adder3.cout
\end{stanza}
}

\column{0.5\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{../getting-started/figs/4_Bit_Adder.jpg}
\end{center}

\begin{itemize}
\item defines interface as series of ports,
\item wires together subcircuits in its constructor.
\end{itemize}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Vecs}
constructing vecs
\begin{stanza}
wire myVec1 : <data type>[<number of elements>]
wire myVec2 = Vec([<elt0>, <elt1>, ...])
\end{stanza}

creating a vec of wires
\begin{stanza}
wire ufix5_vec10 : UInt<5>[10]
\end{stanza}


creating a vec of regs
\begin{stanza}
reg reg_vec32 : UInt<16>[32]
\end{stanza}

writing
\begin{stanza}
reg_vec32[1] := UInt(0)
\end{stanza}

reading
\begin{stanza}
wire reg5 = reg_vec[5]
\end{stanza}

\end{frame}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Vec Shift Reg -- {\tiny problems/ShiftRegister.stanza}}

\begin{itemize}
\item add loadability to shift register
\item change interface to use vec's
\end{itemize}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule ShiftRegisterVec :
  input ins: UInt<1>[4]
  input load: UInt<1>
  input shift: UInt<1>
  output out: UInt<1>

  reg delays: UInt<1>[4]
  when load :
    ;; fill in here ...
  else when shift :
    ;; fill in here ...
  out := delays[3]    
\end{stanza}
}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

% \begin{frame}[fragile]{Stanza Console}
% \begin{FramedVerb}
% \end{FramedVerb}
% \end{frame}

\begin{frame}[fragile]{Defining a Tester}

\begin{columns}
\column{0.4\textwidth}
{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defmodule ByteSelector :
  input in: UInt<32>
  input off: UInt<2>
  output out: UInt<8>
  ...

defn byte-selector-tests () :
  with-tester [t, c] = ByteSelector() :
    for i in 0 to 8 all? :
      val in  = rand(1 << 31)
      val off = rand(4)
      poke(t, c.in,  in)
      poke(t, c.off, off)
      step(t)
      expect(t, c.out, (in >> (off * 8)) & 255)
\end{stanza}
}
\begin{center}
\includegraphics[width=0.8\textwidth]{figs/DUTso.pdf}
\end{center}

\column{0.55\textwidth}
{\lstset{basicstyle={\tiny\ttfamily}}
% defmulti reset (t:Tester, n:Int) -> Int
% defmulti step (t:Tester, n:Int) -> Int
% defmulti peek* (t:Tester, data:Bits, index:Int) -> Streamable<Int>
% defmulti poke* (t:Tester, data:Bits, index:Streamable<Int>) -> Streamable<Int>
\begin{stanza}
defclass Tester
defn Tester (dut:String) -> Tester
defmulti dut (t:Tester) -> String
defmulti step (t:Tester) -> Int
defmulti peek (t:Tester, data:Bits) -> Int
defmulti peek (t:Tester, data:Bits, index:Int) -> Int
defmulti poke (t:Tester, data:Bits, x:Int) -> Int
defmulti poke (t:Tester, data:Bits, i:Int, x:Int) -> Int
defmulti expect (t:Tester, data:Bits, target:Int) -> True|False
defn expect (good:Boolean, msg: Streamable) -> True|False
\end{stanza}
}
\begin{tiny}
\noindent
which binds a tester to a module
and allows users to write tests using the given debug protocol.  In particular, users utilize:
\begin{itemize}
\item \code{poke} to set input port and state values,
\item \code{step} to execute the circuit one time unit,
\item \code{peek} to read port and state values, and
\item \code{expect} to compare peeked circuit values to expected arguments.
\end{itemize}
\end{tiny}

\end{columns}
\end{frame}

\begin{frame}[fragile]{Chipper Workflow}
\begin{center}
\includegraphics[width=0.9\textwidth]{figs/chipper-workflow.pdf} 
\end{center}
\end{frame}

\begin{frame}[fragile]{Simulation Debug Output}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
> cd chipper-tutorial/examples
> make ByteSelector.out
RESET 1 -> 1
WIRE-POKE ByteSelector.in = 0x41a7
WIRE-POKE ByteSelector.off = 0x1
STEP[0] 1 -> 0
WIRE-PEEK ByteSelector.out -> 0x41
EXPECT ByteSelector.out 0x41 -> 65
WIRE-POKE ByteSelector.in = 0x60b7acd9
WIRE-POKE ByteSelector.off = 0x2
STEP[1] 1 -> 0
WIRE-PEEK ByteSelector.out -> 0xb7
EXPECT ByteSelector.out 0xb7 -> 183
WIRE-POKE ByteSelector.in = 0x4431b782
WIRE-POKE ByteSelector.off = 0x0
STEP[2] 1 -> 0
WIRE-PEEK ByteSelector.out -> 0x82
EXPECT ByteSelector.out 0x82 -> 130
...
WIRE-POKE ByteSelector.in = 0x6a5d128c
WIRE-POKE ByteSelector.off = 0x2
STEP[6] 1 -> 0
WIRE-PEEK ByteSelector.out -> 0x5d
EXPECT ByteSelector.out 0x5d -> 93
WIRE-POKE ByteSelector.in = 0x6d7d4b3
WIRE-POKE ByteSelector.off = 0x3
STEP[7] 1 -> 0
WIRE-PEEK ByteSelector.out -> 0x06
EXPECT ByteSelector.out 0x6 -> 6
SUCCESS
\end{stanza}
}

\end{frame}

\begin{frame}{Testbench Ingredients}

Users utilize:
\begin{itemize}
\item \code{poke} to set input port and state values,
\item \code{step} to execute the circuit one time unit,
\item \code{peek} to read port and state values, and
\item \code{expect} to compare peeked circuit values to expected arguments.
\end{itemize}

\end{frame}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Testbench for MaxN -- \tt MaxN.stanza}
\begin{columns}
\column{0.49\textwidth}

\begin{itemize}
\item write a testbench for MaxN
\end{itemize}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule MaxN (n: Int, w: Int) :
  input ins : UInt<w>[n]
  output out : UInt<w>
  defn Max2 (x: UInt, y: UInt) :
    mux(x > y, x, y)
  out := ins.reduce(Max2)
\end{stanza}
}
\begin{stanza}
;; returns random int in 0..lim-1
val x = rand(lim) 
\end{stanza}

\column{0.42\textwidth}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defn MaxNTests () :
  with-tester [t,c] = MaxN() :
    for i in 0 to 10 do :
      for j in 0 to num(c) do :
        ;; FILL THIS IN HERE
        poke(t, c.ins[0], 0)
      ;; FILL THIS IN HERE
      step(1)
      expect(t, c.out, 1)
\end{stanza}
}
\end{columns}
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{Dynamically Accessed Vec}
\begin{stanza}
defmodule DynamicMemorySearch (n:Int, w:Int) :
  input  isWr:   UInt<1>
  input  wrAddr: UInt<sizeof(w)>
  input  isRd:   UInt<1>
  input  data:   UInt<w>
  output done:   UInt<1>
  output rdAddr: UInt<sizeof(w)>

  reg index = UInt<sizeof(w)>(0)
  ;; DEFINE MEM HERE
  wire elt  = UInt(0)
  wire isDone = !(isRd | isWr) & ((elt === data) | (index === UInt(n - 1)))
  ;; FILL IN HERE
  when isRd :
    index := UInt(0)
  else when !(isDone) :
    index := index + UInt(1)
  done    := isDone
  rdAddr  := index
\end{stanza}
\end{frame}

\begin{frame}[fragile]{RAM}
RAM is supported using the \code{cmem} construct

\begin{stanza}
cmem m : UInt<32>[32]
\end{stanza}

\noindent
where
\begin{itemize}
\item writes to Mems are positive-edge-triggered
\item reads are either combinational or positive-edge-triggered
\item ports are created by applying a \code{UInt} index
\end{itemize}
\end{frame}

\begin{frame}[fragile]{32-entry Register File}

\begin{stanza}
cmem regs : UInt<32>[32]
when wrEn :
  regs[wrAddr] := wrData
wire iDat = regs[iAddr]
wire mDat = regs[mAddr]
\end{stanza}

\begin{center}
\includegraphics[height=0.55\textheight]{figs/mem.pdf} 
\end{center}

\end{frame}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Load/Search Mem -- \tt DynamicMemorySearch.stanza}
\begin{stanza}
defmodule DynamicMemorySearch (n:Int, w:Int) :
  input  isWr:   UInt<1>
  input  wrAddr: UInt<sizeof(w)>
  input  isRd:   UInt<1>
  input  data:   UInt<w>
  output done:   UInt<1>
  output rdAddr: UInt<sizeof(w)>

  reg index = UInt<sizeof(w)>(0)
  ;; ...
  wire elt  = vals[index]
  wire isDone = !(isRd | isWr) & ((elt === data) | (index === UInt(n - 1)))
  when isWr :
    vals[wrAddr] := data
  ;; ...
  else when !(isDone) :
    index := index + UInt(1)
  done    := isDone
  rdAddr  := index
\end{stanza}
\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]{Sequential Read Ports}
Sequential read ports are created using sequential memories:
\begin{itemize}
\item reads are delayed one cycle
\end{itemize}

\begin{stanza}
smem ram1r1w : UInt<32>[1024]
when wen: ram1r1w[waddr] := wdata
when ren: eg_raddr := raddr
wire rdata = ram1r1w[reg_raddr]
\end{stanza}

\begin{center}
\includegraphics[height=0.4\textheight]{figs/mem-seq-read.pdf} 
\end{center}

\end{frame}

\begin{frame}[fragile]{Stack}

{\lstset{basicstyle={\footnotesize\ttfamily}}
\begin{stanza}
defmodule Stack (depth:Int) :
  input  push:    UInt<1>
  input  pop:     UInt<1>
  input  en:      UInt<1>
  input  dataIn:  UInt<32>
  output dataOut: UInt<32>

  cmem stack_mem : UInt<32>[depth]
  reg sp = UInt<sizeof(depth)>(0)
  reg out = UInt<32>(0)

  when en :
    when push & ((sp + UInt(1)) < UInt(depth)) :
      stack_mem[sp] := dataIn
      sp := sp + UInt(1)
    else when pop & (sp > UInt(0)) :
      sp := sp - UInt(1)
    when sp > UInt(0) :
      out := stack_mem[sp - UInt(1)]
  dataOut := out
\end{stanza}
}

\end{frame}

\begin{frame}[fragile]{Scripting Hardware Generation}

\begin{columns}
\column{0.5\textwidth}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
;; A n-bit adder with carry in and carry out
defmodule Adder (n:Int) :
   input  a:    UInt<n>
   input  b:    UInt<n>
   input  cin:  UInt<1>
   output sum:  UInt<n>
   output cout: UInt<1>

   wire carry: UInt<1>[n + 1]
   wire sums: UInt<1>[n]
   carry[0] := cin
   for i in 0 to n do :
      inst fa : FullAdder
      fa.a := a[i]
      fa.b := b[i]
      fa.cin := carry[i]
      carry[i + 1] := fa.cout
      sums[i] := fa.sum

   sum := reduce(cat, sums)
   cout := carry[n]
\end{stanza}
}

\column{0.4\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{../getting-started/figs/4_Bit_Adder.jpg}
\end{center}
\end{columns}

\end{frame}

% \input{../talks/microsoft/libs-to-langs-guts-in-stanza.tex}

\setbeamercolor{frametitle}{bg=\frametitleproblemcolor}
\begin{frame}[fragile]{Mul Lookup Table Problem -- \tt Mul.stanza}
\begin{itemize}
\item write 16x16 multiplication table using \code{Vec}
\end{itemize}
\begin{stanza}
defmodule Mul :
  input x : UInt<4>
  input y : UInt<4>
  output z : UInt<8>
  wire tab : UInt<8>[256]

  ;; CALC Z := x * y BY FILLING IN TAB

  z := UInt(0)
\end{stanza}

\end{frame}
\setbeamercolor{frametitle}{bg=\frametitledefaultcolor}

\begin{frame}[fragile]
\frametitle{Valid Wrapper}

\begin{columns}

\column{0.65\textwidth}

\begin{footnotesize}
\begin{stanza}
defbundle Valid<T> :
  output data : T
  output valid : UInt<1>

defmodule GCD :
  input a : UInt<16>
  input b : UInt<16>
  output out : Valid<UInt<16>>
  ...
  out.data  := x
  out.valid := y === UInt(0)
\end{stanza}
\end{footnotesize}

\column{0.3\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/valid.pdf} 
\end{center}

\end{columns}
\note{now gcd had a valid signal on its output.  \\[1cm]
we can generalize this idea by defining a wrapper class that bundles a valid with a data signal. \\[1cm]
now we can rewrite GCD using an interface using this valid wrapper for its output. }

\end{frame}


\begin{frame}[fragile]
\frametitle{Decoupled Wrapper}

\begin{columns}

\column{0.65\textwidth}

\begin{footnotesize}
\begin{stanza}
defbundle Decoupled<T> :
  data : T
  valid : UInt<1>
  flip ready : UInt<1>

defmodule DecoupledGCD :
   input  a: DecoupledIO<UInt<16>>
   input  b: DecoupledIO<UInt<16>>
   output z: DecoupledIO<UInt<16>>

   reg computing = UInt(false)
   reg x: UInt<16>
   reg y: UInt<16>

   a.ready := !(computing)
   b.ready := !(computing)
   z.bits  := UInt(0)
   z.valid := UInt(false)

   ;; ...
\end{stanza}
\end{footnotesize}

\column{0.3\textwidth}

\begin{center}
\includegraphics[width=0.9\textwidth]{figs/decoupled.pdf} 
\end{center}

\end{columns}
\note{Often we need to handle backpressure.
  Decoupled interface handles this.}

\end{frame}

\begin{frame}[fragile]{Debugging Circuits with DecoupledIO}

\begin{itemize}
\item map queues to DecoupledIO's
\item sources pop from queue and push onto circuit  
\item sinks pop data from circuit and push onto queue and 
\item step now first does needed circuit peek/poke's and queue pop/add's
\end{itemize}    

Sources and Sinks are created and added to tester
\begin{scala}
defn Source<?T> (t:Tester, d:DecoupledIO<?T&Data>) ...
defn Sink<?T> (t:Tester, d:DecoupledIO<?T&Data>) ...
defmulti add-ios (t:Tester, ios:Streamable<SmartIO<Data>>) 
\end{scala}    

Sources and Sinks support
\begin{itemize}
\item \verb+add+ -- push onto queue 
\item \verb+pop+ -- pop and return top of queue
\item \verb+peek+ -- return top of queue
\item \verb+clear+ -- remove all queue elements
\item \verb+length+ -- size of queue
\end{itemize}    

\end{frame}

\begin{frame}[fragile]{Decoupled GCD Tester}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defn decoupled-gcd-tests (n:Int) :
  defn gcd (a:Int, b:Int) -> Int :
    if b == 0: a else: gcd(b, a % b)
  with-tester [t, c] = DecoupledGCD() :
    ;; connect queues to decoupled io
    val as = Source(t, c.a)
    val bs = Source(t, c.b)
    val zs = Sink(t, c.z)
    add-ios(t, [as, bs, zs])
    ;; tests and remember correct answers
    val ezs = Vector<Int>()
    for i in 0 to n do :
      val [a, b] = [rand(2, 256), rand(2, 256)]
      add(ezs, gcd(a, b))
      add(as, [a])
      add(bs, [b])
    ;; wait for circuit to consume inputs and produce all answers
    while length(as) > 0 or length(bs) > 0 or length(zs) < length(ezs) :
      step(t)
    ;; check answers
    for i in 0 to length(ezs) all? :
      val rz = pop(zs)
      expect(rz[0] == ezs[i], ["Sum " ezs[i] " GOT " rz[0]])
\end{stanza}
}

\end{frame}

\begin{frame}[fragile]{Sum Accelerator -- {\tt examples/Sum.stanza}}

\begin{columns}
\column{.45\textwidth}
{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
public defbundle SumReq  :
  v   : UInt<32>
  len : UInt<32>

public defbundle SumResp  :
  data : UInt<32>

public defbundle MemReq :
  wr   : UInt<1>
  tag  : UInt<8>
  addr : UInt<32>
  data : UInt<32>

public defbundle MemResp :
  tag  : UInt<8>
  data : UInt<32>
\end{stanza}
}

\column{.45\textwidth}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
public defmodule Sum :
  input  sreq: DecoupledIO<SumReq>
  output srsp: DecoupledIO<SumResp>
  input  mrsp: DecoupledIO<MemResp>
  output mreq: DecoupledIO<MemReq>
  reg a   : UInt<32>
  reg ea  : UInt<32>
  reg n   : UInt<32>
  reg sum : UInt<32>
  reg computing  = UInt(false)
  ...
  when computing :
    sreq.ready := UInt(false)
    when mrsp.valid :
      sum := sum + mrsp.bits.data
      n   := n - UInt(1)
    when a < ea :
      mreq.valid := UInt(true)
      mreq.bits.addr := a
      when mreq.ready :
        a := a + UInt(1)
    else when n === UInt(0) :
      srsp.valid := UInt(true)
      srsp.bits.data := sum
      when srsp.ready :
        sum       := UInt(0)
        computing := UInt(false)
  else when sreq.valid :
    a  := sreq.bits.v
    ea := sreq.bits.v + sreq.bits.len
    n  := sreq.bits.len
    computing := UInt(true)
\end{stanza}
}
\end{columns}

\end{frame}

\begin{frame}[fragile]{SumCore -- {\tt examples/SumCore.stanza}}

{\lstset{basicstyle={\small\ttfamily}}
\begin{stanza}
defmodule SumCore :
  input  sreq: DecoupledIO<SumReq>
  output srsp: DecoupledIO<SumResp>
  input  mrsp: DecoupledIO<MemResp>
  output mreq: DecoupledIO<MemReq>
  inst sum : Sum
  sum.sreq := sreq
  srsp     := sum.srsp
  mreq     := sum.mreq
  sum.mrsp := mrsp
\end{stanza}
}

\end{frame}

\begin{frame}[fragile]{SumCore Tester -- {\tt examples/SumCore.stanza}}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defn sum-core-tests (n:Int) :
  with-tester [t, c] = SumCore() :
    val mrsps = Source(t, c.mrsp)
    val mreqs = Sink(t, c.mreq)
    val sreqs = Source(t, c.sreq)
    val srsps = Sink(t, c.srsp)
    add-ios(t, [mreqs, mrsps, sreqs, srsps])
    for i in 0 to 10 all? :
      val v = to-array(stream({ rand(256) }, 0 to (rand(n - 1) + 1)))
      val r = reduce(plus, 0, v)
      add(sreqs, [0, length(v)])
      while length(sreqs) > 0 or length(srsps) < 1 :
        while length(mreqs) > 0 :
          val mreq = pop(mreqs)
          val [wr, tag, addr, data] = [mreq[0], mreq[1], mreq[2], mreq[3]]
          if wr == 0 :
            add(mrsps, [tag, v[addr]])
        step(t)
      val srsp = pop(srsps)
      expect(srsp[0] == r, ["Sum " r " GOT " srsp[0]])
\end{stanza}
}

\end{frame}

\begin{frame}[fragile]{Memory -- {\tt examples/Memory.stanza}}

\begin{columns}
\column{.35\textwidth}
{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
public defbundle MemReq :
  wr   : UInt<1>
  tag  : UInt<8>
  addr : UInt<32>
  data : UInt<32>

public defbundle MemResp :
  tag  : UInt<8>
  data : UInt<32>
\end{stanza}
}

\column{.55\textwidth}
{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
public defmodule Memory (n: Int) :
  input  req : DecoupledIO<MemReq>
  output rsp : DecoupledIO<MemResp>
  cmem mem : UInt<32>[n]
  req.ready     := rsp.ready
  rsp.valid     := UInt(false)
  rsp.bits.data := UInt(0)
  rsp.bits.tag  := UInt(0)
  when req.valid :
    rsp.valid    := UInt(true)
    rsp.bits.tag := req.bits.tag
    when req.bits.wr :
      rsp.bits.data      := req.bits.data
      mem[req.bits.addr] := req.bits.data
    else :
      rsp.bits.data := mem[req.bits.addr]
\end{stanza}
}
\end{columns}

\end{frame}

\begin{frame}[fragile]{SumSys -- {\tt examples/SumSys.stanza}}

{\lstset{basicstyle={\scriptsize\ttfamily}}
\begin{stanza}
defmodule SumSys (n:Int) :
  input  sreq: DecoupledIO<SumReq>
  output srsp: DecoupledIO<SumResp>
  input  mreq: DecoupledIO<MemReq>
  output mrsp: DecoupledIO<MemResp>
  inst sum   : Sum
  inst mem   : Memory(n)
  val [req, chosen] = arbiter([mreq, sum.mreq])
  fan-out(chosen, mem.rsp, [mrsp, sum.mrsp])
  mem.req     := req
  srsp        := sum.srsp
  sum.sreq    := sreq
\end{stanza}
}
\begin{center}
\includegraphics[height=0.4\textheight]{figs/SumSys.pdf} 
\end{center}

\end{frame}


\begin{frame}[fragile]{Borrowing from Compiler Field}
\begin{columns}
\column{0.45\textwidth}
\begin{center}
\includegraphics[width=0.9\columnwidth]{../talks/retreat-15-06/figs/llvm-logo.png}
\end{center}
\column{0.45\textwidth}
\begin{itemize}
\item Apple Programming Stack
\item NVidia Cuda
\item OpenCL  
\item Cray Chapel
\item Haskell
\item Many backends
\end{itemize}    
\end{columns}
\end{frame}

\begin{frame}[fragile]{LLVM IR}
\begin{columns}
\column{0.4\textwidth}
\begin{bash}
define i32 @mul_add
    (i32 %x, i32 %y, i32 %z) {
entry:
  %tmp = mul i32 %x, %y
  %tmp2 = add i32 %tmp, %z
  ret i32 %tmp2
} 
\end{bash}
\column{0.55\textwidth}
\begin{itemize}
\item SSA-based IR
\item Primitive RISC ISA
\begin{itemize}
\item Regular instructions
\item Easy to write backends  
\end{itemize}
\item Compiler organized as transformations that take LLVM IR and produce LLVM IR
\item IR exposed as file format and API
\item Supports User-defined Transformations
\end{itemize}    
\end{columns}
\end{frame}

\begin{frame}[fragile]{FIRRTL (Li + Izraelevitz)}
\begin{columns}
\column{0.55\textwidth}
\begin{itemize}
\item {\bf F}lexible {\bf I}ntermediate {\bf R}epresentation for {\bf RTL}
\item Focussed Synthesizable RTL
\item Precise File Format and API
\item Micro Passes for Robustness
\item User defined passes
\item Chew Off Biggest Piece of Chipper and make it modular
\end{itemize}    
\column{0.35\textwidth}
{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
circuit GCD :
  module GCD :
    input a : UInt<16>
    input b : UInt<16>
    input e : UInt<1>
    output z : UInt<16>
    output v : UInt<1>
    reg x1 : UInt<16>
    reg y2 : UInt<16>
    node tmp3 = gt(x1, y2)
    when tmp3 :
      node tmp4 = sub-wrap(x1, y2)
      x1 := tmp4      
    else :
      node tmp5 = sub-wrap(y2, x1)
      y2 := tmp5
    when e :
      x1 := a
      y2 := b      
    z := x1
    node tmp6 = eq(y2, UInt<1>(0))
    v := tmp6   
\end{stanza}
}
\end{columns}
\end{frame}

\begin{frame}[fragile]{EDEN Ecosystem}
\begin{columns}
\column{0.4\textwidth}
\begin{itemize}
\item Modular
\item Language Neutral
\begin{itemize}
\item SEJITS $\rightarrow$ FIRRTL
\item Verilog $\rightarrow$ FIRRTL
\item chisel3 $\rightarrow$ FIRRTL
\end{itemize}    
\item Backends
\begin{itemize}
\item LLVM
\item verilog
\item target code  
\end{itemize}    
\item Transformations
\begin{itemize}
\item FAME
\item Rate Balancing  
\item Coverage
\item Snapshot
\end{itemize}    
\item Tools
\begin{itemize}
\item Coverage
\item Visualization
\end{itemize}    
\end{itemize}    
\column{0.5\textwidth}
\begin{center}
\includegraphics[width=0.9\columnwidth]{../talks/retreat-15-06/figs/eden.pdf} \\[1cm]
{\footnotesize{\bf E}lectronic {\bf D}esign of {\bf E}verything {\bf N}icer}
\end{center}
\end{columns}
\end{frame}

\begin{frame}[fragile]{Chipper Approach}
\begin{itemize}
\item macros
\begin{itemize}
\item creates elegant representation
\item creates scaffolding
\end{itemize}
\item handles with AST IR
\begin{itemize}
\item handles are typed and also point to IR
\item IR collected in circuits and modules
\item IR tree data structure easy to print, read, walk
\item explicit file format
\end{itemize}
\end{itemize}

\end{frame}

\begin{frame}[fragile]{Embedding Interface}
\begin{columns}

\column{0.45\textwidth}

chipper
{\lstset{basicstyle={\tiny\ttfamily}}
\begin{scala}
definterface CHExp
defmulti firrtl-exp (e:CHExp) -> fExpression
defmulti type<?T> (e:?T&CHExp) -> Type<T>

definterface Type<T>
defmulti firrtl-type (t:Type) -> fType
defmulti handle<?T> (t:Type<?T>, e:fExpression) -> T
\end{scala}
}

\column{0.45\textwidth}

firrtl
{\lstset{basicstyle={\tiny\ttfamily}}
\begin{scala}
defstruct Circuit :
   modules: List<Module>
   main: Symbol
defstruct Module :
   name: Symbol
   ports: List<Port>
   body: Stmt
definterface Stmt
defstruct DefWire <: Stmt :
   name: Symbol
   type: Type
...
defstruct Node <: Stmt :
   name: Symbol
   value: Expression
...
definterface Expression
defmulti type (e:Expression) -> Type
defstruct Ref <: Expression :
   name: Symbol
   type: Type
defstruct Subfield <: Expression :
   exp: Expression
   name: Symbol
   type: Type
...
definterface Type
defstruct UIntType <: Type :
   width: Width
...
\end{scala}
}
\end{columns}

\end{frame}

\begin{frame}[fragile]{Chipper/FIRRTL Construction}

\begin{columns}

\column{0.45\textwidth}
chipper
\begin{stanza}
UIntVal(1) + UIntVal(1)
\end{stanza}

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defn UIntVal (v:Int) :
  val e = fUIntValue(v, fIntWidth(w))
  handle(UInt(w), e)

defn plus (x:UInt, y:UInt) -> UInt:
  handle(UInt(),
         DefNode(gensym("T"),
                 fDoPrim(fADD-WRAP-OP,
                         list(firrtl-exp(x),
                              firrtl-exp(y)), 
                         ...)
\end{stanza}
}

\column{0.45\textwidth}

firrtl
{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
public defstruct UIntValue <: Expression :
  value: Int
  width: Width

public defstruct DefNode <: Stmt :
   name: Symbol
   value: Expression
\end{stanza}
}

\end{columns}

\end{frame}

\begin{frame}[fragile]{Bundle Expansions}

\begin{stanza}
defbundle Double :
   a: UInt
   b: UInt
\end{stanza}

... expands to ...

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defclass Double <: CHExp
defmulti a (d:Double) -> UInt
defmulti b (d:Double) -> UInt

defn Double (e:Expression) :
   new Double :
      defmethod firrtl-exp (this) : e
      defmethod a (this) :
         UInt(Subfield(e, `a))
      defmethod b (this) :
         UInt(Subfield(e, `b))

defclass DoubleType <: CHType
defn DoubleType () :
   new DoubleType :
      defmethod handle (this, e:Expression) :
         Double(e)
\end{stanza}
}
\end{frame}

\begin{frame}[fragile]{Module Expansions}

\begin{stanza}
defmodule Dual :
   input a: UInt
   output b: UInt
   mybody
\end{stanza}

... expands to ...

{\lstset{basicstyle={\tiny\ttfamily}}
\begin{stanza}
defclass Dual <: CHExp
defmulti a (d:Dual) -> UInt
defmulti b (d:Dual) -> UInt

defn Dual (e:Expression) :
   new Dual :
      defmethod firrtl-exp (this) : e
      defmethod a (this) :
         UInt(Subfield(e, `a))
      defmethod b (this) :
         UInt(Subfield(e, `b))

defclass DualModule <: CHModule
defn DualModule () :
   new DualModule :
      defmethod handle (this, e:Expression) :
         Dual(e)
      defmethod firrtl-module (this) :
         ModuleExp(
            `Dual,
            fn () : mybody)
\end{stanza}
}
\end{frame}

\begin{frame}[fragile]{Chipper vs LMS}
\begin{itemize}
\item hardware types are different than software ones
\item no type complexity
\item no perfect symmetry between compile-time run-time
\end{itemize}
\begin{tabular}{|c|c|}
\hline
{\bf HW} & {\bf SW} \\
\hline
\hline
UInt & BigInt \\
\hline
SInt & BigInt \\
\hline
Vec & Array \\
\hline
Bundle & ??? \\
\hline
\end{tabular}
\end{frame}

\begin{frame}[fragile]{DSL Open Problems}
\begin{itemize}
\item seamlessness
\begin{itemize}
\item looks like domain
\item no leakage 
\item good error reporting
\end{itemize}
\item embedded plus eclipse support
\begin{itemize}
\item want embedding to leverage facilities
\item want automatic tooling
\end{itemize}
\item better hosting language
\begin{itemize}
\item easy to understand
\item powerful
\item base
\item easy/powerful to embed
\end{itemize}
\end{itemize}
\end{frame}

\end{document}
